#include <stdlib.h>
#include <stdio.h>
#include "string.h"
#include "header.h"

//void inorder(struct TreeNode* root, int* res, int* resSize) {
//    if (!root) {
//        return;
//    }
//    inorder(root->left, res, resSize);
//    res[(*resSize)++] = root->val;
//    inorder(root->right, res, resSize);
//}

//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//    int* res = malloc(sizeof(int) * 501);
//    *returnSize = 0;
//    inorder(root, res, returnSize);
//    return res;
//}

void printTree(struct TreeNode *pNode);

void generateTree(struct TreeNode *pNode, char pString[100][100], int start, int count) {

}

int countNum = 1;

void CreatBinaryTree(struct TreeNode *tmp , char pString[100][100],  int count) {
//确认递归的结束的条件,由于是用户输入节点，当用户输入<0时，递归结束
    if (countNum >= count || tmp->val == -1) {
        //节点为空，此处必须写空，不然系统会分配一个不为空的地址
        return;
    }

    tmp->left =  malloc(sizeof(struct TreeNode));
    tmp->left->val = atoi(pString[countNum++]);
    tmp->left->left = NULL;
    tmp->left->right = NULL;

    if (countNum >= count || tmp->val == -1) {
        return;
    }

    tmp->right =  malloc(sizeof(struct TreeNode));
    tmp->right->val = atoi(pString[countNum++]);
    tmp->right->left  = NULL;
    tmp->right->right = NULL;

    CreatBinaryTree(tmp->left, pString,  count);//生成左子树
    CreatBinaryTree(tmp->right, pString,  count);//生成右子树
}

void CreatBinaryTreeBfs(struct TreeNode *tmp , char pString[100][100],  int count) {
    int front = 1;
    int rear = 0;
    int len  = 1;
    while (len != 0) {

    }
}


void inorder(struct TreeNode *root, int *res, int *returnSize) {
    if (!root) {
        return;
    }
    inorder(root->left, res, returnSize);
    res[(*returnSize)++] = root->val;
    printf("%d  ", root->val);
    inorder(root->right, res, returnSize);
}

int *inorderTravelsal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

void getNum(char str[], char retStrArr[100][100], int *count) {    //1.使用strtok()实现分割
    char test[100] = {0};
    strncpy_s(test, sizeof(test) - 1, (str + 1), strlen(str) - 2);
    char *tmp = strtok(test, " ,");
    if (!tmp) {
        *count = 0;
        return;
    } else {
        strcpy_s(retStrArr[(*count)++], sizeof(retStrArr[*count]), tmp);
    }

    while (tmp != NULL) {
        tmp = strtok(NULL, " ,");
        if (NULL == tmp) {
            break;
        }
        if (strcmp(tmp, "null") == 0) {
            strcpy_s(retStrArr[(*count)++], sizeof(retStrArr[*count]), "-1");

        } else {
            strcpy_s(retStrArr[(*count)++], sizeof(retStrArr[*count]), tmp);

        }
    }
}

int main() {


//    struct TreeNode *root = malloc(sizeof(struct TreeNode));
//    root->val = 1;
//
//    root->left = NULL;
//    root->right = malloc(sizeof(struct TreeNode));
//    root->right->val = 2;
//
//    root->right->left = malloc(sizeof(struct TreeNode));
//    root->right->left->val = 3;
//    root->right->left->left = NULL;
//    root->right->left->right = NULL;
//    root->right->right = NULL;

//    int ret = 0;
//    inorderTravelsal(root, &ret);
//    printf("len %d\n", ret);

//    printTree(root);

    char str[] = "[1,null,2,3,6, 4,5,7,8]";

    printf("\n\n\n%s\n", "start strtok string.");
    int count = 0;
    char retStrArr[100][100] = {0};
    getNum(str, retStrArr, &count);
    for (int i = 0; i < count; ++i) {
        printf("%s\n", retStrArr[i]);
    }

    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = atoi(retStrArr[0]);
    struct TreeNode *tmp = root;
    root->left = NULL;
    root->right  = NULL;
    CreatBinaryTree(tmp, retStrArr, count);

//    printTree(root);
int ret = 0;
    inorderTravelsal(root, &ret);
}


//void generateTree(struct TreeNode *pNode, char pString[100][100], int start, int count) {
//    if (start < count) {
//        if (strcmp(pString[start], "null") == 0) {
//            pNode = NULL;
//            return;
//        } else {
//            pNode->val = atoi(pString[start]);
//        }
//    } else {
//        pNode = NULL;
//        return;
//    }
//    pNode->left = malloc(sizeof (struct TreeNode));
//    generateTree(pNode->left, pString, start * 2 + 1, count);
//    pNode->right = malloc(sizeof (struct TreeNode));
//    generateTree(pNode->right, pString, start + 2 + 2, count);
////    pNode->left = malloc(sizeof (struct  TreeNode));
////    pNode->right = malloc(sizeof (struct  TreeNode));
//
//}

void printTree(struct TreeNode *pNode) {
    if (!pNode) {
        return;
    }
    printf_s("%d  ", pNode->val);
    printTree(pNode->left);
    printTree(pNode->right);
}


